//
// Created by Lenovo on 2024/3/15.
//
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:

    int n;
    //各个结点的入度
    vector<int> indegree;
    //并查集
    int p[1010];
    //初始化并查集
    void init(){
        for(int i=1;i<=n;i++) p[i]=i;
    }
    //查
    int find(int x){
        if(p[x]==x) return x;
        else return p[x]=find(p[x]);
    }
    
    //判断删除掉这条边后还是不是一颗树
    bool isTreeAfterRemoveEdge(vector<vector<int>>& edges,int deleteEdge){
        init();
        for(int i=0;i<edges.size();i++){
            if(i==deleteEdge) continue;
            int ru = find(edges[i][0]);
            int rv = find(edges[i][1]);
            if(ru==rv){      //构成有向环了，说明不是树了
                return false;
            }
            p[rv]=ru;
        }
        return true;
    }

    //在有向图里找到删除的那条边，使其变成树
    vector<int> getRemoveEdge(vector<vector<int>>& edges){
        init();
        for(int i=0;i<edges.size();i++){
            int ru = find(edges[i][0]);
            int rv = find(edges[i][1]);
            if(ru==rv){     //构成有向边了，就是要删除的边
                return edges[i];
            }
            p[rv]=ru;
        }
        return {};
    }


    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        n=edges.size();
        indegree=vector<int>(n+1,0);
        //统计各个节点的入度
        for(int i=0;i<edges.size();i++){
            indegree[edges[i][1]]++;
        }
        //记录入度为2的节点的边
        vector<int> vec;
        for(int i=edges.size()-1;i>=0;i--){
            if(indegree[edges[i][1]]==2){
                vec.push_back(i);
            }
        }
        //有入度为2的顶点，一定是2条边里面删掉一条
        if(vec.size()>0){
            if(isTreeAfterRemoveEdge(edges,vec[0])){
                return edges[vec[0]];
            }else{
                return edges[vec[1]];
            }
        }
        //没有入度为2的顶点，一定是存在有向环，找到构成环的边删除
        return getRemoveEdge(edges);
    }
};